package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TPath;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.Arrays;

/**
 *
 */
@XClassic
@KDynamicPlanning
@TPath
public class LC62_UniquePaths {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            return uniquePath0(m - 1, n - 1, dp);
        }

        private int uniquePath0(int i, int j, int[][] dp) {
            if (dp[i][j] == 0) {
                if(i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = uniquePath0(i - 1, j, dp) + uniquePath0(i, j - 1, dp);
                }
            }
            return dp[i][j];
        }
    }

    @XOptimal
    static
    class Solution1 {
        public int uniquePaths(int m, int n) {
            int[] dp = new int[n];
            Arrays.fill(dp, 1);
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[j] += dp[j - 1];
                }
            }
            return dp[n - 1];
        }
    }
}
